package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/19 14:15
 *
 机器人的运动范围:BFS
 在矩阵中移动，坐标不大于threshold

1,2,3
3
 */





import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;

public class Main45 {
    class Node{
        int x,y;
        Node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }

    public int getBitsSum(int x){
        int ans=0;
        while (x!=0){
            ans+=x%10;
            x/=10;
        }
        return ans;
    }


    public int movingCount(int threshold, int rows, int cols) {
        if(threshold==0)return 1;
        Queue<Node>queue=new LinkedList<>();
        int dx[]={1,-1,0,0};
        int dy[]={0,0,-1,1};
        boolean vis[][]=new boolean[rows][cols];
        int ans=0;
        queue.offer(new Node(0,0));

        while (!queue.isEmpty()){
            Node node=queue.poll();
            int x=node.x,y=node.y;
            ans++;
            //
            for(int i=0;i<4;++i){
                int xx=dx[i]+x;
                int yy=dy[i]+y;
                if(xx>=0&&xx<rows&&yy>=0&&yy<cols&&!vis[xx][yy]){
                    //坐标数位值和
                    if(getBitsSum(xx)+getBitsSum(yy)<=threshold){
                        queue.offer(new Node(xx,yy));
                    }
                }
            }
        }
        return ans;
    }
    /*
    //力扣模式不支持该包import javafx.util.Pair;

    public int movingCount(int threshold, int rows, int cols) {
        if(threshold==0)return 1;
        Queue<Pair<Integer,Integer>>queue=new LinkedList<>();
        int dx[]={1,-1,0,0};
        int dy[]={0,0,-1,1};
        boolean vis[][]=new boolean[rows][cols];
        int ans=0;
        queue.offer(new Pair<>(0,0));

        while (!queue.isEmpty()){
            Pair<Integer,Integer>pair=queue.poll();
            int x=pair.getKey(),y=pair.getValue();
            ans++;
            //
            for(int i=0;i<4;++i){
                int xx=dx[i]+x;
                int yy=dy[i]+y;
                if(xx>=0&&xx<rows&&yy>=0&&yy<cols&&!vis[xx][yy]){
                    //坐标数位值和
                    if(getBitsSum(xx)+getBitsSum(yy)<=threshold){
                        queue.offer(new Pair<>(xx,yy));
                    }
                }
            }
        }
        return ans;
    }

     */
    public static void main(String[] args) {
    }
}
